package basic.courseLearn07.problem;

import basic.courseLearn07.Edge;
import basic.courseLearn07.Graph;
import basic.courseLearn07.Node;
import lombok.*;
import org.junit.Test;

import java.util.*;

//单源最短路径问题，Dijkstra算法
public class DijkstraAlgorithm {

    public Map<Node, Integer> dijkstra(Graph graph, Node root){
        //1. 定义map，不存在代表距离无穷大；set，用于记录已经处理过的节点
        Map<Node, Integer> map = new HashMap<Node, Integer>();
        HashSet<Node> set = new HashSet<>();
        //2. root开始，距离为0
        map.put(root, 0);
        MinHeap minHeap = new MinHeap();
        minHeap.init();
        minHeap.insert(new Struct(root, 0));
        //3. 计算Map中最小的距离节点，并且不在set中
//        Node minNode = calMinDistance(map, set);
        Node minNode = calMinDistance_MinHeap(minHeap, set);

        //4. 循环
        while (minNode!= null) {
            //4.1 获得distance，root到minNode的距离
            int distance = map.get(minNode);
            //4.2 遍历相邻节点
            for (Node toNode : minNode.nexts) {
                //4.2.1 判断是否在map中
                if (!map.containsKey(toNode)){
                    //加入map
                    map.put(toNode, distance + getWeight(graph, minNode, toNode));
                    minHeap.insert(new Struct(toNode, distance + getWeight(graph, minNode, toNode)));
                }
                //4.2.2 更新距离
                map.put(toNode, Math.min(map.get(toNode), distance + getWeight(graph, minNode, toNode)));
                minHeap.update(new Struct(toNode, Math.min(map.get(toNode), distance + getWeight(graph, minNode, toNode))));
            }
            //4.3 标记节点已访问
            set.add(minNode);
            //4.4 更新最小距离点
//            minNode = calMinDistance(map, set);
            minNode = calMinDistance_MinHeap(minHeap, set);
        }
        return map;
    }

    //计算最小距离节点，在Map中，并且不在Set中
    private Node calMinDistance(Map<Node, Integer> map, HashSet<Node> set) {
        //1. 定义node和距离
        Node node = null;
        int minDistance = Integer.MAX_VALUE;
        //2. 遍历Map
        for (Node tempNode : map.keySet()) {
            if ( !set.contains(tempNode) && map.get(tempNode) != null && map.get(tempNode) < minDistance) {
                node = tempNode;
                minDistance = map.get(tempNode);
            }
        }
        //3. 返回node
        return node;
    }

    //计算最小距离节点，在Map中，并且不在Set中
    private Node calMinDistance_MinHeap(MinHeap heap, HashSet<Node> set) {
        //1. 定义node和距离
        Struct res=null;
        //2. 遍历Map
        while(true){
            res = heap.pop();
            if (res==null||!set.contains(res.getNode())){
                break;
            }
        }
        //3. 返回node
        return (res==null)?null:res.getNode();
    }




    //获取边的权重
    public Integer getWeight(Graph graph, Node start, Node end){
        Iterator<Edge> iterator = graph.edges.iterator();
        while(iterator.hasNext()){
            Edge edge = iterator.next();
            if(edge.from == start && edge.to == end){
                return edge.weight;
            }
        }
        return null;
    }




    @Test
    public void test(){
        Graph graph = new Graph();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);


        Edge edge1 = new Edge(1, node1, node2);
        Edge edge2 = new Edge(3, node1, node3);

        Edge edge3 = new Edge(1, node2, node1);
        Edge edge4 = new Edge(6, node2, node4);
        Edge edge5 = new Edge(4, node2, node5);

        Edge edge6 = new Edge(3, node3, node1);
        Edge edge7 = new Edge(5, node3, node4);
        Edge edge8 = new Edge(1, node3, node5);

        Edge edge9  = new Edge(6, node4, node2);
        Edge edge10 = new Edge(5, node4, node3);
        Edge edge11 = new Edge(7, node4, node6);

        Edge edge12 = new Edge(4, node5, node2);
        Edge edge13 = new Edge(1, node5, node3);
        Edge edge14 = new Edge(5, node5, node6);

        HashMap<Integer, Node> map = new HashMap<>();

        node1.addNext(node2);
        node1.addNext(node3);


        node2.addNext(node1);
        node2.addNext(node4);
        node2.addNext(node5);

        node3.addNext(node1);
        node3.addNext(node4);
        node3.addNext(node5);

        node4.addNext(node2);
        node4.addNext(node3);
        node4.addNext(node6);

        node5.addNext(node2);
        node5.addNext(node3);
        node5.addNext(node6);

        map.put(1, node1);
        map.put(2, node2);
        map.put(3, node3);
        map.put(4, node4);
        map.put(5, node5);
        map.put(6, node6);
        graph.setNodes(map);


        HashSet<Edge> edges = new HashSet<>();
        edges.add(edge1);
        edges.add(edge2);
        edges.add(edge3);
        edges.add(edge4);
        edges.add(edge5);
        edges.add(edge6);
        edges.add(edge7);
        edges.add(edge8);
        edges.add(edge9);
        edges.add(edge10);
        edges.add(edge11);
        edges.add(edge12);
        edges.add(edge13);
        edges.add(edge14);

        graph.setEdges(edges);

        Map<Node, Integer> map1 = dijkstra(graph, node1);
        map1.keySet().forEach(node -> System.out.println(node.value + " : " + map1.get(node)));


    }

    @AllArgsConstructor
    @NoArgsConstructor
    @Data
    public class Struct{
        public Node node;

        public int distance;

    }


    public class MinHeap{

        public Struct[] heap ;
        public int heapTop;

        //向下调整
        public void downHeap(int i){
            //1. 循环
            while (true){
                //1.1 和左右孩子的最小值进行比较
                int minIndex;
                if (i*2+1 <= heapTop && i*2+2 <= heapTop){
                    minIndex = heap[i*2+1].getDistance()<heap[i*2+2].getDistance() ? i*2+1 : i*2+2;
                }else if (i*2+1 <= heapTop && i*2+2 > heapTop){
                    minIndex = i*2+1;
                }else{
                    break;
                }
                if (heap[i].getDistance() < heap[minIndex].getDistance()){
                    break;
                }else{
                    swap(heap, i, minIndex);
                    i = minIndex;
                }
            }
        }

        //向上调整
        public void upHeap(int i){
            if (i<=0){
                return;
            }
            while (true){
                //比父节点更小
                if (heap[i].getDistance() < heap[(i-1)/2].getDistance()){
                    swap(heap, i, (i-1)/2);
                    i = (i-1)/2;
                }else{
                    break;
                }
                if (i==0){
                    break;
                }
            }

        }

        //交换两个元素
        public void swap(Struct[] arr,int i, int j){
            if (i!=j){
                Struct temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        //插入元素
        public void insert(Struct value){
            heap[++heapTop]=value;
            upHeap(heapTop);
        }

        //弹出元素
        public Struct pop(){
            if (heapTop<0){
                return null;
            }
            Struct temp = heap[0];
            heap[0] = heap[heapTop--];
            downHeap(0);
            return temp;
        }

        //初始化
        public void init(){
            heapTop=-1;
            heap = new Struct[1000000];
        }

        //更新元素
        public void update(Struct value){
            int index = -1;
            for (int i = 0; i <= heapTop; i++) {
                if (heap[i].getNode().equals(value.getNode())) {
                    index = i;
                    break;
                }
            }
            if (index!=-1){
                heap[index].setDistance(value.getDistance());
                upHeap(index);
                downHeap(index);
            }
        }

    }







}
